'''
归并排序：
把数组拆分成2半，把左边和右边继续递归拆分，直到不能拆分了，变成一个。
拆分成最小单位后，把2个单位合并，有序合并。返回后，和右边的继续有序合并。
直到最后完成。

不需要确定中间值，只是把序列拆分成2组，然后通过2组合并时进行排序。
'''
def merge_sort(nums):
    print("nums=", nums)
    if len(nums) <= 1:
        return nums
    
    # 分割数组
    mid = len(nums) // 2
    print("mid=", mid, "len=", len(nums))

    print("left=", nums[:mid])

    # 把左边的都合并
    left = merge_sort(nums[:mid])

    print("right=", nums[mid:])

    # 把右边的都合并
    right = merge_sort(nums[mid:])
    print("left merge=", left)
    print("right merge=", right)
    
    # 合并两个有序数组
    final = merge(left, right)
    print("final merge=", final)
    return final

# 合并2个有序数组，遍历，从中获取一个更小的，放到数组中，最后把剩余部分追加进去。
def merge(left, right):
    result = []
    i = j = 0
    
    # 合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 将剩余的元素添加到结果中
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

def sortArray(nums):
    return merge_sort(nums)

def test_sortArray():
    # 测试示例 1
    assert sortArray([5, 2, 3, 1]) == [1, 2, 3, 5], "测试示例 1 失败"
    
    # 测试示例 2
    assert sortArray([5, 1, 1, 2, 0, 0]) == [0, 0, 1, 1, 2, 5], "测试示例 2 失败"
    
    # 测试示例 3: 已经有序的数组
    assert sortArray([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5], "测试示例 3 失败"
    
    # 测试示例 4: 逆序数组
    assert sortArray([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5], "测试示例 4 失败"
    
    # 测试示例 5: 包含重复元素的数组
    assert sortArray([4, 2, 2, 8, 3, 3, 1]) == [1, 2, 2, 3, 3, 4, 8], "测试示例 5 失败"
    
    # 测试示例 6: 空数组
    assert sortArray([]) == [], "测试示例 6 失败"
    
    # 测试示例 7: 只有一个元素的数组
    assert sortArray([1]) == [1], "测试示例 7 失败"
    
    print("所有测试用例通过！")

# 运行测试
test_sortArray()